home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / game / board / Crafty-15.19.lha / crafty-15.19 / src / iterate.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  17KB  |  415 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "chess.h"
  5. #include "data.h"
  6. #include "epdglue.h"
  7.  
  8. /* last modified 07/08/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   Iterate() is the routine used to drive the iterated search.  it repeatedly *
  13. *   calls search, incrementing the search depth after each call, until either  *
  14. *   time is exhausted or the maximum set search depth is reached.              *
  15. *                                                                              *
  16. ********************************************************************************
  17. */
  18. int Iterate(int wtm, int search_type, int root_list_done)
  19. {
  20.   int *mvp;
  21.   int i, value=0, time_used;
  22.   int twtm, used_w, used_b;
  23.   int correct, correct_count, material=0, sorted, temp;
  24.   TREE *tree=local[0];
  25.  
  26. /*
  27.  ----------------------------------------------------------
  28. |                                                          |
  29. |  initialize.                                             |
  30. |                                                          |
  31. |  produce the root move list, which is ordered and kept   |
  32. |  for the duration of this search (the order may change   |
  33. |  as new best moves are backed up to the root of course.) |
  34. |                                                          |
  35.  ----------------------------------------------------------
  36. */
  37.   time_abort=0;
  38.   abort_search=0;
  39.   book_move=0;
  40.   program_start_time=ReadClock(time_type);
  41.   start_time=ReadClock(time_type);
  42.   cpu_time_used=0;
  43.   elapsed_start=ReadClock(elapsed);
  44.   PreEvaluate(tree,wtm);
  45.   tree->nodes_searched=0;
  46.   tree->fail_high=0;
  47.   tree->fail_high_first=0;
  48.   if (booking || !Book(tree,wtm,root_list_done)) do {
  49.     if (abort_search) break;
  50.     if (!root_list_done) RootMoveList(wtm);
  51.     if (EGTB_draw) EGTB_use=0;
  52.     else EGTB_use=EGTBlimit;
  53.     if (EGTBlimit && !EGTB_use)
  54.       Print(128,"Drawn at root, trying for swindle.\n");
  55.     correct_count=0;
  56.     burp=15*100;
  57.     transposition_id=(transposition_id+1)&7;
  58.     if (!transposition_id) transposition_id++;
  59.     program_start_time=ReadClock(time_type);
  60.     start_time=ReadClock(time_type);
  61.     cpu_percent=0;
  62.     elapsed_start=ReadClock(elapsed);
  63.     next_time_check=nodes_between_time_checks;
  64.     tree->evaluations=0;
  65. #if !defined(FAST)
  66.     tree->transposition_hits=0;
  67.     tree->transposition_probes=0;
  68.     tree->pawn_probes=0;
  69.     tree->pawn_hits=0;
  70. #endif
  71.     tree->tb_probes=0;
  72.     tree->tb_probes_successful=0;
  73.     tree->check_extensions_done=0;
  74.     tree->recapture_extensions_done=0;
  75.     tree->passed_pawn_extensions_done=0;
  76.     tree->one_reply_extensions_done=0;
  77.     root_wtm=wtm;
  78.     root_total_white_pieces=TotalWhitePieces;
  79.     root_total_white_pawns=TotalWhitePawns;
  80.     root_total_black_pieces=TotalBlackPieces;
  81.     root_total_black_pawns=TotalBlackPawns;
  82. /*
  83.  ----------------------------------------------------------
  84. |                                                          |
  85. |  if there are no legal moves, it is either mate or draw  |
  86. |  depending on whether the side to move is in check or    |
  87. |  not (mate or stalemate.)                                |
  88. |                                                          |
  89.  ----------------------------------------------------------
  90. */
  91.     if (tree->last[0] == tree->last[1]) {
  92.       program_end_time=ReadClock(time_type);
  93.       tree->pv[0].path_length=0;
  94.       tree->pv[0].path_iteration_depth=10;
  95.       if (Check(wtm)) {
  96.         root_value=-(MATE-1);
  97.         last_search_value=-(MATE-1);
  98.       }
  99.       else {
  100.         root_value=DrawScore(crafty_is_white);
  101.         last_search_value=DrawScore(crafty_is_white);
  102.       }
  103.       Print(6,"              depth   time  score   variation\n");
  104.       Print(6,"                                    (no moves)\n");
  105.       tree->nodes_searched=1;
  106.       return(root_value);
  107.     }
  108. /*
  109.  ----------------------------------------------------------
  110. |                                                          |
  111. |   now set the search time and iteratively call Search()  |
  112. |   to analyze the position deeper and deeper.  note that  |
  113. |   Search() is called with an alpha/beta window roughly   |
  114. |   1/3 of a pawn on either side of the score last         |
  115. |   returned by search.  also, after the first root move   |
  116. |   is searched, this window is collapsed to n and n+1     |
  117. |   (where n is the value for the first root move.)  often |
  118. |   a better move is found, which causes search to return  |
  119. |   <beta> as the score.  we then relax beta depending on  |
  120. |   its value:  if beta = alpha+1, set beta to alpha+1/3   |
  121. |   of a pawn;  if beta = alpha+1/3 pawn, then set beta to |
  122. |   + infinity.                                            |
  123. |                                                          |
  124.  ----------------------------------------------------------
  125. */
  126.     TimeSet(search_type);
  127.     iteration_depth=1;
  128.     if (last_pv.path_iteration_depth > 1)
  129.       iteration_depth=last_pv.path_iteration_depth+1;
  130.     Print(6,"              depth   time  score   variation (%d)\n",
  131.           iteration_depth);
  132.     time_abort=0;
  133.     abort_search=0;
  134.     program_start_time=ReadClock(time_type);
  135.     start_time=ReadClock(time_type);
  136.     elapsed_start=ReadClock(elapsed);
  137. /*
  138.  ----------------------------------------------------------
  139. |                                                          |
  140. |   now install the learned position information in the    |
  141. |   hash table.                                            |
  142. |                                                          |
  143.  ----------------------------------------------------------
  144. */
  145.     LearnPositionLoad(tree);
  146. /*
  147.  ----------------------------------------------------------
  148. |                                                          |
  149. |   set the initial search bounds based on the last search |
  150. |   or default values.                                     |
  151. |                                                          |
  152.  ----------------------------------------------------------
  153. */
  154.     tree->pv[0]=last_pv;
  155.     if (iteration_depth > 1) {
  156.       root_alpha=last_value-40;
  157.       root_value=last_value-40;
  158.       root_beta=last_value+40;
  159.     }
  160.     else {
  161.       root_alpha=-MATE-1;
  162.       root_value=-MATE-1;
  163.       root_beta=MATE+1;
  164.     }
  165.     for (i=0;i<256;i++) tree->root_nodes[i]=0;
  166. /*
  167.  ----------------------------------------------------------
  168. |                                                          |
  169. |   if we are using multiple threads, and they have not    |
  170. |   been started yet, then start them now as the search    |
  171. |   is ready to begin.                                     |
  172. |                                                          |
  173.  ----------------------------------------------------------
  174. */
  175. #if defined(SMP)
  176.     if (max_threads>smp_idle+1) {
  177.       pthread_t pt;
  178.       int proc;
  179.       if (!EGTB_use || !(TotalPieces<=5 && EGTBScore(tree, 1, wtm, &i))) {
  180.         for (proc=smp_threads+1;proc<max_threads;proc++) {
  181.           Print(128,"starting thread %d\n",proc);
  182.           thread[proc]=0;
  183.           tfork(pt,ThreadInit,(void *) proc);
  184.           smp_threads++;
  185.         }
  186.       }
  187.     }
  188. #endif
  189.     for (;iteration_depth<=60;iteration_depth++) {
  190. /*
  191.  ----------------------------------------------------------
  192. |                                                          |
  193. |   now install the old PV into the hash table so that     |
  194. |   these moves will be followed first.                    |
  195. |                                                          |
  196.  ----------------------------------------------------------
  197. */
  198.       twtm=wtm;
  199.       for (i=1;i<=(int) tree->pv[0].path_length;i++) {
  200.         tree->pv[i]=tree->pv[i-1];
  201.         if (!LegalMove(tree,i,twtm,tree->pv[i].path[i])) {
  202.           Print(4095,"ERROR, not installing bogus move at ply=%d\n",i);
  203.           Print(4095,"not installing from=%d  to=%d  piece=%d\n",
  204.                 From(tree->pv[i].path[i]), To(tree->pv[i].path[i]),
  205.                 Piece(tree->pv[i].path[i]));
  206.           break;
  207.         }
  208.         StorePV(tree, i, twtm);
  209.         MakeMove(tree, i,tree->pv[0].path[i],twtm);
  210.         twtm=ChangeSide(twtm);